home *** CD-ROM | disk | FTP | other *** search
- /**************************** vheap.c **********************************
-
- Purpose: Implement a "virtual heap": a combination of stacks and
- a heap.
-
- Provenance: Written and tested by Q. Chen and E. Fox, March 1991.
- Edited and tested by S. Wartik, April 1991.
- Revised and tested by S. Wartik, July 1991.
-
- Notes: The point of the combination is that a stack is a more
- efficient data structure. Vertices of low degree
- (specifically, those <= NO_STACKS) are stored in stacks,
- since they are more common. Vertices of high degree are
- stored in the heap.
-
- **/
-
- #include <math.h>
- #include <stdio.h>
-
- /* The following aims to define INT_MAX as the maximum value of
- * type "int" for the hardware on which the program is being compiled.
- */
- #ifdef __STDC__
- #include <limits.h>
- #else
- /* According to a comment in the file "values.h" on a Sun-4 (which
- * unfortunately isn't widely available), the following works on any
- * binary representation where the high-order bit contains the sign.
- */
- # ifndef INT_MAX
- # if gcos
- # define BITSPERBYTE 9
- # else
- # define BITSPERBYTE 8
- # endif
- # define BITS(type) (BITSPERBYTE * (int)sizeof(type))
- # define HIBITI (1 << BITS(int) - 1)
- # define INT_MAX (~HIBITI)
- # endif
- #endif
-
- #include "types.h"
- #include "support.h"
- #include "vheap.h"
-
-
- #define NO_STACKS 6 /* The number of stacks in use. */
- #define DEF_SIZE 10 /* The default size of a heap or a stack. */
-
- typedef struct { /* Stack data structure. */
- int stackTop, /* Stack top. */
- stackSize; /* Allocated stack area size. */
- vertexType **stackRep; /* Stack area. */
- } stackType;
-
- typedef struct { /* Heap cell data structure. */
- int degree; /* Key field, containing vertex's degree. */
- vertexType *vertex; /* Info field, holding vertex's address. */
- } heapCell;
-
- typedef struct { /* Heap data structure. */
- int heapTop, /* Heap top. */
- heapSize; /* Allocated heap area size. */
- heapCell *heapRep; /* Heap area. */
- } heapType;
-
- stackType stacks[NO_STACKS]; /* The stacks of the virtual heap. */
- heapType heap; /* The heap portion. */
-
- #ifdef __STDC__
-
- extern void push( stackType *stack, vertexType *vertex );
- extern int pop( stackType *stack, vertexType **vertex );
- extern void enter_heap( int degree, vertexType *vertex );
- extern int remove_from_heap( vertexType **vertex );
-
- #else
-
- extern void push();
- extern int pop();
- extern void enter_heap();
- extern int remove_from_heap();
-
- #endif
-
-
-
- /***********************************************************************
-
- add_to_vheap( vertex, degree )
-
- Return: void
-
- Purpose: Add a vertex of a specified degree to the virtual heap.
-
- **/
-
- void add_to_vheap( vertex, degree )
- vertexType *vertex; /* in: a vertex to be added. */
- int degree; /* in: the vertex's degree. */
- {
- if ( degree > NO_STACKS )
- enter_heap( degree, vertex );
- else
- push( &stacks[degree-1], vertex );
- }
-
- /*************************************************************************
-
- max_degree_vertex( vertex )
-
- Return: int -- NORM if a vertex could be found, ABNORM if the
- virtual heap (stacks and heap) is empty.
-
- Purpose: Find the unvisited vertex with maximal degree from the
- virtual heap. Place it in "vertex".
-
- Plan: First check the heap; remove_from_heap() automatically
- removes a vertex of maximal degree. If the heap is
- empty, try the stacks, one at a time.
- **/
-
- int max_degree_vertex( vertex )
- vertexType **vertex; /* out: the vertex found. */
- {
- int i;
-
- if ( remove_from_heap( vertex ) == NORM ) /* heap empty? */
- return(NORM);
-
- for( i = NO_STACKS - 1; i >= 0; i-- ) /* stacks empty? */
- if ( pop( &stacks[i], vertex ) == NORM )
- return (NORM);
-
- return(ABNORM); /* No node at all. The component has been processed. */
- }
-
-
- /*************************************************************************
-
- push(stack, vertex )
-
- Return: void
-
- Purpose: Push a vertex pointer onto a stack.
- **/
-
- static void push(stack, vertex)
- stackType *stack; /* in out: the stack. */
- vertexType *vertex; /* in: the vertex. */
- {
- stack->stackTop++;
-
- /* Expand stack if it doesn't have enough space. */
- if ( stack->stackTop >= stack->stackSize ) {
- fprintf(stderr, "Warning: stack overflow. Re-allocating.\n");
- stack->stackSize *= 2;
- stack->stackRep =
- (vertexType**)ownrealloc( (char *)stack->stackRep,
- sizeof(vertexType*) * stack->stackSize );
- }
-
- stack->stackRep[stack->stackTop] = vertex;
- }
-
-
- /*************************************************************************
-
- pop( stack, vertex )
-
- Return: int -- Index of a vertex.
-
- Purpose: Pop up a vertex pointer from the stack. Return -1 if the stack
- was empty, 0 if it wasn't.
- **/
-
- static int pop( stack, vertex )
- stackType *stack;
- vertexType **vertex;
- {
- if ( stack->stackTop == -1 )
- return(-1); /* stack empty */
-
- *vertex = stack->stackRep[stack->stackTop--];
- return(0); /* stack not empty */
- }
-
- /*************************************************************************
-
- enter_heap( degree, vertex )
-
- Return: void
-
- Purpose: Insert a vertex pointer and its degree into the heap.
-
- **/
-
- static void enter_heap( degree, vertex )
- int degree; /* in: the degree of the node. */
- vertexType *vertex; /* in: the vertex pointer. */
- {
- int k = heap.heapTop++ ;
-
- if ( k >= heap.heapSize ) {
- heap.heapSize = 2 * heap.heapSize;
- heap.heapRep =
- (heapCell*)ownrealloc( (char *)heap.heapRep,
- sizeof(heapCell) * heap.heapSize );
- }
-
- heap.heapRep[k].degree = degree;
- heap.heapRep[k].vertex = vertex;
-
- while ( heap.heapRep[k/2].degree <= degree ) {
- heap.heapRep[k].degree = heap.heapRep[k/2].degree;
- heap.heapRep[k].vertex = heap.heapRep[k/2].vertex;
- k /= 2;
- }
-
- heap.heapRep[k].degree = degree;
- heap.heapRep[k].vertex = vertex;
- }
-
-
- /*************************************************************************
-
- remove_from_heap( vertex )
-
- Return: int -- -1 if the heap is empty when the routine is called,
- 0 if it isn't.
-
- Purpose: Remove a vertex of maximal degree from the heap, and
- return it.
- **/
-
- static int remove_from_heap( vertex )
- vertexType **vertex; /* out: the vertex selected. */
- {
- int k, j; /* Iterators through the heap. */
- heapCell tempCell; /* Heap element currently being examined. */
-
- if ( heap.heapTop == 1 ) return(-1);
-
- *vertex = heap.heapRep[1].vertex;
- heap.heapTop--;
-
- tempCell.degree =
- heap.heapRep[1].degree= heap.heapRep[heap.heapTop].degree;
- tempCell.vertex = heap.heapRep[1].vertex =
- heap.heapRep[heap.heapTop].vertex;
-
- k = 1; /* Go down the heap. */
- while ( k <= heap.heapTop / 2 ) {
- j = 2 * k;
- if ( (j < heap.heapTop ) &&
- (heap.heapRep[j].degree< heap.heapRep[j+1].degree) )
- j++;
- if ( tempCell.degree > heap.heapRep[j].degree )
- break;
- heap.heapRep[k].degree = heap.heapRep[j].degree;
- heap.heapRep[k].vertex = heap.heapRep[j].vertex;
- k = j;
- } /* end of while */
-
- heap.heapRep[k].degree = tempCell.degree;
- heap.heapRep[k].vertex = tempCell.vertex;
- return(0);
- }
-
-
- /*************************************************************************
-
- initialize_vheap()
-
- Return: void
-
- Purpose: Set the heap and stacks to their empty states.
- **/
-
- void initialize_vheap()
- {
- int i;
-
- heap.heapRep[0].degree = INT_MAX;
- heap.heapTop = 1;
-
- for ( i = 1; i < heap.heapSize; i++ ) {
- heap.heapRep[i].degree = 0;
- heap.heapRep[i].vertex = 0;
- }
-
- for ( i = 0; i < NO_STACKS; stacks[i++].stackTop = -1 );
- }
-
-
-
- /*************************************************************************
-
- free_vheap()
-
- Return: void
-
- Purpose: Deallocate space for stacks and heap.
- **/
-
- void free_vheap()
- {
- int i;
-
- for ( i = 0; i < NO_STACKS; free((char *)stacks[i++].stackRep) );
-
- free( (char *)heap.heapRep );
- }
-
-
-
- /*************************************************************************
-
- allocate_vheap( no_arcs, no_vertices )
-
- Return: void
-
- Purpose: Estimate and allocate space for the heap and the stacks.
- **/
-
- void allocate_vheap( no_arcs, no_vertices )
- int no_arcs, /* in: number of arcs. */
- no_vertices; /* in: number of vertices. */
- {
- int i, /* iteration variable. */
- sum = 0; /* partial sum of degree. */
- double lambda, /* lambda = |E| / ( |V| / 2 ) */
- Pr0, /* Pr0 = Pr(X = 0) */
- Pri; /* Pri = Pr(X = i) */
-
- lambda = (double)(2*no_arcs) / (double)no_vertices;
- Pr0 = Pri = exp(-lambda); /* Compute Pr(x = 0). */
-
- for ( i = 1; i <= NO_STACKS; i++ ) { /* Compute the expected number */
- Pri *= lambda/(double)(i); /* of nodes of degree 1, 2, ..., */
- /* NO_STACKS. */
- stacks[i-1].stackSize = (int) 2 * no_vertices * Pri;
- sum += stacks[i-1].stackSize ;
- }
-
- for ( i = 0; i < NO_STACKS; i++ ) { /* Allocate stack space. */
- if ( stacks[i].stackSize <= 0 ) stacks[i].stackSize = DEF_SIZE;
- stacks[i].stackRep =
- (vertexType**) owncalloc( stacks[i].stackSize, sizeof(vertexType*) );
- }
-
- heap.heapSize = no_vertices - sum - (int) 2 * no_vertices * Pr0;
- if ( heap.heapSize <= 0 ) heap.heapSize = DEF_SIZE;
- heap.heapRep = /* Allocate heap space. */
- (heapCell*) owncalloc( heap.heapSize, sizeof(heapCell) );
- }
-